#define DEBUG
#pragma GCC optimize("3")
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=8;

int change(int map[][maxn+1], bool book[maxn+1][maxn+1], int x, int y, int oldc, int newc, int n) {
  const int fx[4][2]={{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
  int ret=1;
  map[x][y] = newc;
  book[x][y] = true;
  for (int i=0; i<4; i++) {
    int nx=x+fx[i][0], ny=y+fx[i][1];
    if (nx>0 && ny>0 && nx<=n && ny<=n && map[nx][ny]==oldc) {
      ret += change(map, book, nx, ny, oldc, newc, n);
    }
  }
  return ret;
}

int getSize(int map[maxn+1][maxn+1], bool book[maxn+1][maxn+1], int x, int y, int n) {
  const int fx[4][2]={{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
  book[x][y] = true;
  int ret=1;
  for (int i=0; i<4; i++) {
    int nx=x+fx[i][0], ny=y+fx[i][1];
    if (nx>0 && ny>0 && nx<=n && ny<=n && !book[nx][ny]) {
      ret += getSize(map, book, nx, ny, n);
    }
  }
  return ret;
}

int h(const int map[maxn+1][maxn+1], bool book[][maxn+1], int n) {
  static bool c[6];
  for (int i=0; i<6; i++) {
    c[i] = false;
  }
  int ans=0;
  for (int i=1; i<=n; i++) {
    for (int j=1; j<=n; j++) {
      if (!book[i][j] && !c[map[i][j]]) {
	c[map[i][j]] = true;
	ans++;
      }
    }
  }
  return ans;
}

int solve(int now, int size, const int status[maxn+1][maxn+1], int limit, int n) {
  int newmap[maxn+1][maxn+1];
  static bool book[maxn+1][maxn+1];
  memset(book, 0, sizeof(book));
  if (h(status, book, n)==1) {
    return now;
  }
  for (int i=0; i<=5; i++) {
    if (i==status[1][1]) {
      continue;
    }
    for (int j=1; j<=n; j++) {
      for (int k=1; k<=n; k++) {
	newmap[j][k] = status[j][k];
	book[j][k] = false;
      }
    }
    int nsize=change(newmap, book, 1, 1, newmap[1][1], i, n);
    if (size==nsize) {
      continue;
    }
    int t=h(newmap, book, n);
    if (now+1+t<=limit) {
      int temp=solve(now+1, nsize, newmap, limit, n);
      if (temp>=0) {
	return temp;
      }
    }
  }
  return -1;
}

int main() {
#ifdef DEBUG
  freopen("3422.in", "r", stdin);
  freopen("3422.out", "w", stdout);
#endif

  int n;
  for (scanf("%d", &n); n; scanf("%d", &n)) {
    static int map[maxn+1][maxn+1];
    for (int i=1; i<=n; i++) {
      for (int j=1; j<=n; j++) {
	scanf("%d", &map[i][j]);
      }
    }
    int ans=-1;
    static bool book[maxn+1][maxn+1];
    memset(book, 0, sizeof(book));
    int size=getSize(map, book, 1, 1, n);
    for (int i=1; ans<0; i++) {
      ans = solve(0, size, map, i, n);
    }
    printf("%d\n", ans);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
